package oj;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

//栈的压入、弹出序列：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
//1. 0<=pushV.length == popV.length <=1000
//2. -1000<=pushV[i]<=1000
//3. pushV 的所有数字均不相同
public class Solution_JZ31 {
    //将 int[] 转为 ArrayList<Integer>
    private static List<Integer> intArrayToList(int[] array){
        List<Integer> ans = new ArrayList<>();
        for(int e : array){
            ans.add(e);
        }
        return ans;
    }
    public static boolean isPopOrder(int [] pushA,int [] popA) {

        if(pushA.length != popA.length){
            return false;
        }

        List<Integer> pushAList = intArrayToList(pushA);
        List<Integer> popAList = intArrayToList(popA);

        //定义栈
        Deque<Integer> stack = new LinkedList<>();

        //遍历每个出栈序列的元素
        while(!popAList.isEmpty()){
            int popE = popAList.remove(0);
            while(stack.isEmpty() || stack.peek() != popE){
                if(pushAList.isEmpty()){
                    return false;
                }
                int pushE = pushAList.remove(0);
                stack.push(pushE);
            }
            stack.pop();
        }
        return true;
    }

    public static void main(String[] args) {
        int[] array1 = {1,2,3,4,5};
        int[] array2 = {4,3,5,1,2};
        System.out.println(isPopOrder(array1, array2));

    }
}
